class Node():
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 添加数据
t = head = Node()
t.next = Node(1)
t = t.next
t.next = Node(2)
t = t.next
t.next = Node(3)
t = t.next
t.next = Node(4)
t = t.next
# 打印添加的数据
t = head
while t:
    print(t.val, end=" ")
    t = t.next
print()

# 反转链表
p1 = head 
p2 = p1.next if p1 else None 
# 将第一个node的next置为空
p1.next = None

while p2:
    # p1 -> p2 - > p3
    # 临时记录p2的下一个节点
    tmp = p2.next
    # p2的下一个节点指向p1,即指向p2的前一个节点
    p2.next = p1
    # 移动p1, p2
    p1 = p2
    p2 = tmp

# 打印反转的结果
while p1:
    print(p1.val, end=" ")
    p1 = p1.next
print()

# 上面解法会修改原有的链表，在不修改的情况下可以用栈：后进先出
# 递归本质就是一个栈
def reverse_node(node):
    if node:
        if node.next:
            reverse_node(node.next)
        print(node.val)

# 添加数据
t = head = Node()
t.next = Node(1)
t = t.next
t.next = Node(2)
t = t.next
t.next = Node(3)
t = t.next
t.next = Node(4)
reverse_node(head)